home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / db / esm-3.1 / esm-3 / usr / local / sm / src / serverlib / lm / checkDeadlock.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-05-05  |  6.4 KB  |  239 lines
  1. /*
  2.  *   $RCSfile: checkDeadlock.c,v $  
  3.  *   $Revision: 1.1.1.1 $  
  4.  *   $Date: 1996/05/04 21:55:53 $      
  5.  */ 
  6. /**********************************************************************
  7. * EXODUS Database Toolkit Software
  8. * Copyright (c) 1991 Computer Sciences Department, University of
  9. *                    Wisconsin -- Madison
  10. * All Rights Reserved.
  11. *
  12. * Permission to use, copy, modify and distribute this software and its
  13. * documentation is hereby granted, provided that both the copyright
  14. * notice and this permission notice appear in all copies of the
  15. * software, derivative works or modified versions, and any portions
  16. * thereof, and that both notices appear in supporting documentation.
  17. *
  18. * THE COMPUTER SCIENCES DEPARTMENT OF THE UNIVERSITY OF WISCONSIN --
  19. * MADISON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" CONDITION.  
  20. * THE DEPARTMENT DISCLAIMS ANY LIABILITY OF ANY KIND FOR ANY DAMAGES
  21. * WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  22. *
  23. * The EXODUS Project Group requests users of this software to return 
  24. * any improvements or extensions that they make to:
  25. *
  26. *   EXODUS Project Group 
  27. *     c/o David J. DeWitt and Michael J. Carey
  28. *   Computer Sciences Department
  29. *   University of Wisconsin -- Madison
  30. *   Madison, WI 53706
  31. *
  32. *     or exodus@cs.wisc.edu
  33. *
  34. * In addition, the EXODUS Project Group requests that users grant the 
  35. * Computer Sciences Department rights to redistribute these changes.
  36. **********************************************************************/
  37.  
  38. #include "sysdefs.h"
  39. #include "ess.h"
  40. #include "checking.h"
  41. #include "trace.h"
  42. #include "error.h"
  43. #include "list.h"
  44. #include "pool.h"
  45. #include "tid.h"
  46. #include "io.h"
  47. #include "lock.h"
  48. #include "object.h"
  49. #include "msgdefs.h"
  50. #include "thread.h"
  51. #include "semaphore.h"
  52. #include "link.h"
  53. #include "lsn.h"
  54. #include "latch.h"
  55. #include "bf.h"
  56. #include "volume.h"
  57. #include "trans.h"
  58. #include "lm_intfuncs.h"
  59. #include "lm_extfuncs.h"
  60. #include "lm_globals.h"
  61.  
  62. #define TRAILMAX     10
  63.  
  64.  
  65.  int
  66. checkDeadlock (
  67.  
  68.     register TRANSREC    *targetTrans,
  69.     register LOCKENTRY    *holderEntry 
  70. )
  71. {
  72.  
  73.     register LOCKENTRY    *lockEntry;
  74.     register TRANSREC    *holderTrans;
  75.     register LOCKENTRY    **top;
  76.     LOCKENTRY* DLtrail[TRAILMAX];
  77.     int DLtrailCnt = 0;
  78.     int detected = FALSE;
  79.     
  80.     DLtrail[DLtrailCnt++] = holderEntry;
  81.  
  82.  
  83.     TRPRINT(TR_LOCK, TR_LEVEL_1, ("tid:%x", GETTID(targetTrans)));
  84.  
  85.     /*
  86.      *    increment the visited count
  87.      */
  88.     DeadlockVisitCount++;
  89.  
  90.     /*
  91.      *    the holder entry must me non-null
  92.      */
  93.     CHECK_LOCKENTRY_MAGIC(holderEntry);
  94.  
  95.     /*
  96.      *    loop until all reachable nodes have been visited
  97.      */
  98.     for (top = &(DeadlockStack[0]); ! detected;)    {
  99.  
  100.         /*
  101.          *    search down the list
  102.          */
  103.         while (holderEntry != NULL)    {
  104.  
  105.             TRPRINT(TR_LOCK, TR_LEVEL_2, ("lockid:%x:%x:%x",
  106.                     holderEntry->lockHeader->hashList.lockid.lockid.word1,
  107.                     holderEntry->lockHeader->hashList.lockid.lockid.word2,
  108.                     holderEntry->lockHeader->hashList.lockid.lockid.word3));
  109.  
  110.             CHECK_LOCKENTRY_MAGIC(holderEntry);
  111.  
  112.             holderTrans = holderEntry->headerList.transRec;
  113.             CHECK_TRANSREC_MAGIC(holderTrans);
  114.             TRPRINT(TR_LOCK, TR_LEVEL_2, 
  115.                             ("holder tid:%x", GETTID(holderTrans)));
  116.  
  117.             if (holderTrans == targetTrans)    {
  118.  
  119.                 /*
  120.                  *    we have gotten back so have deadlock
  121.                  */
  122.                 detected = TRUE;
  123.                 break;
  124.             }
  125.  
  126.  
  127.             if (NOT_VISITED(holderTrans))    {
  128.  
  129.                 TRPRINT(TR_LOCK, TR_LEVEL_2, ("transaction not visited"));
  130.  
  131.                 SET_VISITED(holderTrans);
  132.  
  133.                 /*
  134.                  *    check to see if the transaction is in lock wait
  135.                  */
  136.                 if (LIST_NOT_EMPTY( &(holderTrans->lockWaitList) ) ||
  137.                     LIST_NOT_EMPTY( &(holderTrans->lockUpgradeList) ))    {
  138.  
  139.                     TRPRINT(TR_LOCK, TR_LEVEL_2, ("transaction in lock wait"));
  140.  
  141.                     SM_ASSERT(LEVEL_3, 
  142.                                 top < &(DeadlockStack[DEAD_STACK_SIZE - 1]));
  143.  
  144.                     /*
  145.                      *    push the holder entry on the stack
  146.                      */
  147.                     *(top++) = (LOCKENTRY *) 
  148.                             NEXT_LIST_ELEMENT(&(holderEntry->headerList.list));
  149.  
  150.                     /*
  151.                      *    check to see if this is a wait or an upgrade
  152.                      */
  153.                     if (LIST_NOT_EMPTY( &(holderTrans->lockWaitList))) {
  154.                         lockEntry = (LOCKENTRY*)
  155.                               FIRST_LIST_ELEMENT(&(holderTrans->lockWaitList)); 
  156.                     } else {
  157.                         /* 
  158.                          *    Upgrade entries contain are identical to 
  159.                          *    other entries except that the lockHeader
  160.                          *    pointer points to the lock entry of the
  161.                          *  held lock instead of the actuall lock
  162.                          *    header.
  163.                          */
  164.                         lockEntry = (LOCKENTRY*) ( 
  165.                                         ((LOCKENTRY*) FIRST_LIST_ELEMENT(&(holderTrans->lockUpgradeList)))->lockHeader);
  166.                     }
  167.                     CHECK_LOCKENTRY_MAGIC(lockEntry);
  168.  
  169.                     /*
  170.                      *    get a pointer to the list of lock holders
  171.                      */
  172.                     CHECK_LOCKHEADER_MAGIC(lockEntry->lockHeader);
  173.                     holderEntry = (LOCKENTRY *) NEXT_LIST_ELEMENT( 
  174.                                     &(lockEntry->lockHeader->grantedList) );
  175.                     CHECK_LOCKHEADER_MAGIC(holderEntry->lockHeader);
  176.  
  177.                     DLtrail[DLtrailCnt++] = holderEntry;
  178.                     SM_ASSERT(LEVEL_1, DLtrailCnt <= TRAILMAX);
  179.                     continue;
  180.                 }
  181.             }
  182.  
  183.             /*
  184.              *    look at the next element in the list
  185.              */
  186.             holderEntry = (LOCKENTRY *) NEXT_LIST_ELEMENT( 
  187.                                         &(holderEntry->headerList.list));
  188.         }
  189.         
  190.         /*
  191.          *    check if we have traversed all nodes
  192.          */
  193.         if (top > DeadlockStack)  
  194.             holderEntry = * (--top);   /* pop off the stack */
  195.         else
  196.             break;
  197.     }
  198.     
  199.     if (detected)  {
  200.         /*
  201.          *     deadlock detected !!
  202.          */
  203.         int pageLockOnly = TRUE;
  204.         int i;
  205.         LOCKID* lockIdPtr;
  206.         fprintf(sm_ErrorStream, "SERVER: deadlock detected -- aborting a transaction.\n");
  207.         fprintf(sm_ErrorStream, "  %d locks are involved in the deadlock: \n", DLtrailCnt);
  208.         fprintf(sm_ErrorStream, "    TRANS                 LOCK\n");
  209.         fprintf(sm_ErrorStream, "   -------         -----------------\n");
  210.         for (i = 0; i < DLtrailCnt; i++)  {
  211.             holderEntry = DLtrail[i];
  212.             holderTrans = holderEntry->headerList.transRec;
  213.             lockIdPtr = & holderEntry->lockHeader->hashList.lockid;
  214.             fprintf(sm_ErrorStream, "     %3d           %s\n", holderTrans->tid,
  215.                                             printLockId(*lockIdPtr));
  216.             if (lockIdPtr->page.type != PAGE_LOCK)
  217.                 pageLockOnly = FALSE;
  218.             }
  219.         if (pageLockOnly)  {
  220.             SM_ERROR(TYPE_USER, esmCAUSEDPHANTOMDEADLOCK);
  221.             for (i = 1; i < DLtrailCnt; i++)  {
  222.                 holderTrans = DLtrail[i]->headerList.transRec;
  223.                 while (LIST_NOT_EMPTY(&holderTrans->lockWaitList))  {
  224.                     holderEntry = (LOCKENTRY*)
  225.                         FIRST_LIST_ELEMENT(& holderTrans->lockWaitList);
  226.                     CHECK_LOCKENTRY_MAGIC(holderEntry);
  227.                     freeLockWaiter(holderEntry, esmPHANTOMDEADLOCK);
  228.                     }
  229.                 }
  230.             }
  231.         else {
  232.             SM_ERROR(TYPE_USER, esmLOCKCAUSEDDEADLOCK);
  233.             DLtrailCnt = 0;
  234.             }
  235.         }
  236.     
  237.     return detected;    
  238. }
  239.